/**
 * 给定数组A，执行Q个操作：
 * 每次操作给定i和x，将Ai改成x，并将A排序去重
 * 假定现在A的长度为n，则将等差数列n,...,1分别加到Ai上
 * 再排序去重，再加，直到只剩一个数为止
 * 对每次操作，输出最后剩下的这个数。
 * 将Ai改成x是有后效的，排序去重相加操作无后效
 * 每次相加会使得相邻差少一，因此要加的次数就是最大差，最大值肯定是每次加一，
 * 因此最后这个数就是最大差加最大值。
 * 实际上就是在数组修改操作之中，时刻维护数组的最大值与最大差
 * 使用两个map，分别记录数组值的数量，与相邻值之差的数量。
 * 似乎用multiset更简单一些，注意特判N==1
 */
#include <bits/stdc++.h>
using namespace std;

using llt = long long;
using pii = pair<int, int>;

int N;
vector<int> A, B;
int Q;
map<int, int> Cha, V;

inline void dec(map<int, int> & m, map<int, int>::iterator it){
    if(0 == --it->second){
        m.erase(it);
    }
}

void remove(int x){
    auto it = V.find(x);
    assert(it != V.end());

    if(it->second > 2)return (void)(--it->second);
    if(it->second == 2){
        it->second = 1;
        auto chaIt = Cha.find(0);
        dec(Cha, chaIt);
        return;
    }

    if(it != V.begin()){
        auto jt = it;
        --jt;
        auto cha = it->first - jt->first;
        auto chaIt = Cha.find(cha);
        assert(chaIt != Cha.end());
        dec(Cha, chaIt);
    }

    if(it != --V.end()){
        auto jt = it;
        ++jt;
        auto cha = jt->first - it->first;
        auto chaIt = Cha.find(cha);
        assert(chaIt != Cha.end());
        dec(Cha, chaIt);
    }

    if(it != V.begin() and it != --V.end()){
        auto jt = it, kt = it;
        --jt, ++kt;
        ++Cha[kt->first - jt->first];
    }

    dec(V, it);
    return;
}

void insert(int x){
    auto it = V.find(x);
    if(it != V.end()){
        if(it->second >= 2) return (void)(++it->second);

        it->second = 2;
        ++Cha[0];
        return;
    } 

    it = V.insert(it, {x, 1});

    if(it != V.begin()){
        auto jt = it;
        --jt;
        auto cha = it->first - jt->first;    
        ++Cha[cha];  
    }

    if(it != --V.end()){
        auto jt = it;
        ++jt;
        auto cha = jt->first - it->first;
        ++Cha[cha];
    }

    if(it != V.begin() and it != --V.end()){
        auto jt = it, kt = it;
        --jt, ++kt;
        auto cha = kt->first - jt->first;
        auto chaIt = Cha.find(cha);
        assert(chaIt != Cha.end());
        dec(Cha, chaIt);
    }

    return;
}

int proc(int pos, int x){
    if(1 == A.size()) return A[0] = x;

    remove(A[pos]);
    insert(A[pos] = x);

    return (--Cha.end())->first + (--V.end())->first;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("z.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(0);
    int nofkase = 1; 
    cin >> nofkase;
    for(int kase=1;kase<=nofkase;++kase){
        cin >> N;
        A.assign(N, 0);
        for(auto & i : A) cin >> i;

        B.assign(N, 0);
        copy(A.begin(), A.end(), B.begin());
        sort(B.begin(), B.end());

        Cha.clear(); V.clear();
        ++V[B[0]];
        for(int i=1;i<N;++i) ++V[B[i]], ++Cha[B[i] - B[i - 1]];

        cin >> Q;
        for(int pos,x,q=1;q<=Q;++q){
            cin >> pos >> x;
            // cout << q << ": ";
            auto tmp = proc(pos - 1, x);
            cout << tmp << " ";
        }
        cout << endl;
    }
    return 0;
}